﻿
namespace Leetcode.N1751;
public class Solution
{
    public int MaxValue(int[][] events, int k)
    {
        events = events.OrderBy(i => i[1]).ToArray();
        var vals = new int[events.Length + 1][];
        vals[0] = new int[k + 1];

        for (int j = 1; j < vals.Length; j++)
        {
            vals[j] = new int[k + 1];

            int find = 0;
            for (int n = j - 1; n > 0; n--)
            {
                if (events[n - 1][1] < events[j - 1][0])
                {
                    find = n;
                    break;
                }
            }

            for (int i = 1; i <= k; i++)
            {
                vals[j][i] = Math.Max(vals[find][i - 1] + events[j - 1][2], vals[j - 1][i]);
            }
        }
        return vals[vals.Length - 1][k];
    }
}